import javax.swing.plaf.IconUIResource;

public class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        ListNode list = list1.val > list2.val ? list2 : list1;
        ListNode cur = list;
        if (list == cur1) {
            cur1 = cur1.next;
        } else {
            cur2 = cur2.next;
        }

        while (cur1 != null && cur2 != null) {
            if (cur1.val < cur2.val) {
                cur.next = cur1;
                cur = cur.next;
                cur1 = cur1.next;
            } else {
                cur.next = cur2;
                cur = cur.next;
                cur2 = cur2.next;
            }
        }

        if (cur1 == null) {
            cur.next = cur2;
        } else {
            cur.next = cur1;
        }

        return list;
    }

    public ListNode FindKthToTail(ListNode head, int k) {

        if (head == null) {
            return null;
        }
        if (k <= 0) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        while (k != 0 && fast != null) {
            fast = fast.next;
            k--;
        }
        if (k != 0) {
            return null;
        }

        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;

    }

    public ListNode middleNode(ListNode head) {

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null) {
            if (fast.next == null) {
                return slow;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode reverseList(ListNode head) {

        if (head == null || head.next == null) {
            return head;
        }

        ListNode cur = head;
        ListNode curNext = cur.next;
        while (curNext != null) {
            ListNode tmp = curNext.next;
            curNext.next = cur;
            cur = curNext;
            curNext = tmp;
        }
        head.next = null;
        return cur;

    }

    public ListNode removeElements(ListNode head, int val) {
        while (head != null && head.val == val) {
            head = head.next;
        }
        if (head == null) {
            return null;
        }
        ListNode cur = head;
        while (cur.next != null) {
            while (cur.next.val == val) {
                cur.next = cur.next.next;
                if (cur.next == null) {
                    return head;
                }
            }
            cur = cur.next;
        }
        return head;
    }

    public ListNode detectCycle(ListNode head) {

        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (fast == slow) {
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }

    public boolean hasCycle(ListNode head) {

        if (head == null || head.next == null || head.next.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    public int size(ListNode head) {
        ListNode cur = head;
        int len = 0;
        while (cur != null) {
            cur = cur.next;
            len++;
        }
        return len;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if (headB == null || headA == null) {
            return null;
        }
        int lenA = size(headA);
        int lenB = size(headB);

        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int len = lenA - lenB;
        if (len < 0) {
            ListNode tmp = cur1;
            cur1 = cur2;
            cur2 = tmp;
            len = -len;
        }

        while (len > 0) {
            cur1 = cur1.next;
            len--;
        }

        while (cur1 != null) {
            if (cur1 == cur2) {
                return cur1;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return null;
    }

    public boolean chkPalindrome(ListNode A) {
        // write code here
        if (A == null) {
            return false;
        }
        if (A.next == null) {
            return true;
        }

        ListNode slow = A;
        ListNode fast = A;

        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (fast == null) {
                break;
            }
        }

        ListNode slowNext = slow.next;
        while (slowNext != null) {
            ListNode tmp = slowNext.next;
            slowNext.next = slow;
            slow = slowNext;
            slowNext = tmp;
        }

        ListNode cur = A;
        while (cur != slow) {
            if (cur.val != slow.val) {
                return false;
            }
            if (cur.next == slow) {
                return true;
            }
            cur = cur.next;
            slow = slow.next;
        }
        return true;
    }

    public ListNode partition(ListNode pHead, int x) {
        // write code here

        if (pHead == null || pHead.next == null) {
            return pHead;
        }

        ListNode end1 = null;//小于x
        ListNode end2 = null;//大于x
        ListNode cur = pHead;
        ListNode cur1 = null;
        ListNode cur2 = null;


        while (cur != null) {
            if (cur.val < x) {
                if(cur1 == null){
                    cur1 = cur;
                    end1 = cur;
                }else{
                    end1.next = cur;
                    end1 = end1.next;
                }
            } else {
                if(cur2 == null){
                    cur2 = cur;
                    end2 = cur;
                }else{
                    end2.next = cur;
                    end2 = end2.next;
                }
            }
            cur = cur.next;
        }

        if(cur1 == null || cur2 == null){
            return pHead;
        }
        end2.next = null;
        end1.next = cur2;
        return cur1;

    }
}

